class Solution {
public:
    //用一个前缀数组存a[i]之前的乘积
    //用一个后缀数组存a[i]之后的乘积
    //b[i]=前缀数组[i]*后缀数组[i]
    //以下代码对空间做了优化，省略了前缀数组和后缀数组的空间开销
    vector<int> multiply(const vector<int>& a) {
        int len=a.size();
        vector<int>b(len,0);
        //b存储前缀之积
        b[0]=1;
        for(int i=1;i<len;i++)
        {
            b[i]=a[i-1]*b[i-1];
        }
        //r存后缀之积
        int r=1;
        for(int i=len-1;i>=0;i--)
        {
            b[i]=b[i]*r;
            r=r*a[i];
        }
        return b;
    }
};